package com.jml.排序;

/**
 * [1,3,4,2,5] 1左边比1小的数，没有；
 * 3左边比3小的数，1；
 * 4左边比4小的数，1、3；
 * 2左边比2小的数，1；
 * 5左边比5小的数，1、3、4、2；
 * 所以小和为1+1+3+1+1+3+4+2=16
 *
 * 分析：
 *  	1,3,4,5,6,7
 * 		有5个数比1大  5*1
 * 		有四个数比3大  4*3
 * 		有三个数比4大，3*4
 * 		有两个数比5大 2*5
 * 		有一个数比6大 1*6
 * 		小和为  1*5 + 3*4 + 3*4 + 3*4 + 2*5 + 1*6
 */
public class 归并排序小和问题test {

	public static void main(String[] args) {
		System.out.println("-----------------------------");
		int arr1[]={7,2,6,3,8,9};
		int i1 = myselfMergeSort(arr1);
		System.out.println(i1);
		for (int i : arr1){
			System.out.print(i+"-");
		}
	}


	private static int myselfMergeSort(int[] arr) {
		if(arr==null || arr.length<2){
			return 0;
		}

		return myselfMergeSort(arr,0,arr.length-1);

	}
	private static int myselfMergeSort(int[] arr, int left, int right) {
		if(left==right){
			return 0;
		}
		int mid = (right+left)/2;
		return myselfMergeSort(arr,left,mid)+ myselfMergeSort(arr,mid+1,right)+ myselfMerge(arr,left,right,mid);
	}
	private static int myselfMerge(int[] arr, int left, int right, int mid) {
		int[] help = new int[right-left+1];
		int i = 0;
		//左侧部分最小
		int p1 = left;
		//右侧部分最小
		int p2 = mid + 1;
		int result=0;
		while (p1<=mid&&p2<=right){
			if(arr[p1]<arr[p2]){
				result+=(right-p2+1)*arr[p1];
				help[i]=arr[p1];
				p1++;
			}else{
				help[i]=arr[p2];
				p2++;
			}
			i++;
		}

		while(p1<=mid){
			help[i]=arr[p1];
			p1++;
			i++;
		}
		while(p2<=right){
			help[i]=arr[p2];
			p2++;
			i++;
		}
		for (int j = 0; j < help.length; j++) {
			arr[left+j] = help[j];
		}
		return result;
	}

}
